#include "graph.c"
#include <stdlib.h>
#include <stdio.h>

void PrintPath(int S, int W, int LAST[])
{
    int V;

    if (W == S)
    {
        printf("%d", S);
        return;
    }
    V = LAST[W];
    if (!V)  //if (_______) {
    {
        printf("no path");
    }
    PrintPath(S, V, LAST); //PrintPath(_______, ________, LAST);
    printf("-%d", W);	  //printf("-%d", ______);

    return;
}


void main()
{
    int N; //NO. of vertexes
    Graph G;
    int *LAST;
    int S, W;

    G = CreateUndirectGraph();
    N = NumOfVex(G);
    LAST = (int *)malloc(sizeof(int) * (N + 1));
    printf("Source:");
    scanf("%d", &S);

    Shortest(G, S, LAST); //LAST is used to record the path from SOURCE TO DESTINATION
    while (1)
    {
        printf("Destination:");
        scanf("%d", &W);
        if (!W)
            break;			   //0 means the program is over
        PrintPath(S, W, LAST); //print the shortest path from S to W
        printf("\n");
    }

    return;
}
